Field of the Invention
This application relates to sorting.
Description of the Related Art
The widely accepted value for the minimum number of comparison operations to sort a large list of N items is N log 2(N). Different algorithms don't improve on the N log 2(N) barrier, but provide opportunities to perform sorting of the list and also provide other measures during the process such as median and mean. Regardless, to sort a very large list of one billion items, for example, still requires roughly 30B comparisons. Each of these comparisons can also require many clock cycles of the computing system. 30B comparisons might actually take 300B clocked operations. In Big Data analytics, weather prediction, nuclear calculations, astrophysics, genetics, public health, and many other disciplines, there is a frequent need to sort very large datasets. This further implies computational resources than can literally fill buildings with racks of servers to service these needs. To the extent one can improve on this N log 2(N) limitation, or otherwise improve sorting operations, one can improve on the capital infrastructure and associated operational costs for computing systems.